package Algorithm.A5;
/*
* @Author :lcy
* @Description :
* @Date 2021/11/27 19:53
*/

import java.util.Scanner;

public class Investment {
    //项目投资问题，动态规划法，投资五万元。
    //算法为三层嵌套循环，Xk共有x+1项，fk(Xk) + Fk-1(X – Xk)有x+1项，所以有x+1次加，x项比较
    public static void main(String[] args) {
        int F[][] = {{0,0,0,0,0,0},
                {0,0,0,0,0,0},
                {0,0,0,0,0,0},
                {0,0,0,0,0,0},
                {0,0,0,0,0,0}};//向前i个项目投资j万元的最大收益
        int X[][] = { {0,0,0,0,0,0},
                {0,0,0,0,0,0},
                {0,0,0,0,0,0},
                {0,0,0,0,0,0},
                {0,0,0,0,0,0}};//投资j万元最大收益时投资项目i的钱的数量
        int f[][] = { {0,0,0,0,0,0},
                {0,11,12,13,14,15},
                {0,0,5,10,15,20},
                {0,2,10,30,32,40},
                {0,20,21,22,23,24}};
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入投资的金额（万元）:");
        int m = sc.nextInt();
        for (int i = 0; i < 5; i++) {
            F[i][0] = 0;
        }
        for (int i = 0; i <= m; i++) {
            F[1][i] = f[1][i];
            X[1][i] = i;
        }

        for (int i = 2; i <= 4; i++) {
            for (int j = 1; j <= m; j++) {
                F[i][j] = 0;
                int t;
                for (int k = 0; k <= j; k++) {
                    t = f[i][k] + F[i - 1][j - k];
                    if (t > F[i][j]) {
                        F[i][j] = t;
                        X[i][j] = k;
                    }
                }
            }
        }

        int sum = 0;
        for (int i = 4; i >= 1; i--) {
            int invest = X[i][m - sum];
            System.out.println("第"+i+"个项目投资"+invest+"万元");
            sum += invest;
        }
    }
}
